// https://www.lintcode.com/problem/unique-paths/

public class Solution {
    /**
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    public int uniquePaths(int m, int n) {
        // write your code here
        int[][] cache = new int[m][];
        for (int i = 0; i < m; ++i) {
            cache[i] = new int[n];
            for (int j = 0; j < n; ++j) {
                cache[i][j] = 0;
            }
        }
        cache[0][0] = 1;
        return _uniquePaths(m - 1, n - 1, cache);
    }
    
    private int _uniquePaths(int row, int col, int[][] cache) {
        if (cache[row][col] > 0) {
            return cache[row][col];
        }
        int ret = 0;
        if (row > 0) {
            ret += _uniquePaths(row - 1, col, cache);
        }
        if (col > 0) {
            ret += _uniquePaths(row, col - 1, cache);
        }
        cache[row][col] = ret;
        return ret;
    }
}